#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort,max,min
#include <iostream>       // cout,cin
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    int maxProduct(vector<string> &words) {
        int size = words.size();

        int *stats = new int[size];  // 存储每个单词包含字母状态的数组
        int *lens = new int[size];  // 存储每个单词长度的数组
        memset(stats, 0, sizeof(int) * size);  // 将存储状态的内存全部设置为0
        for (int i = 0; i < size; i++) {
            for (char ch : words[i]) {
                stats[i] |= (1 << (ch - 97));  // 压缩每个单词包含字母状态
            }
            lens[i] = words[i].size();
        }

        // 两层循环寻找结果
        int ans = 0;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if ((stats[i] & stats[j]) == 0) {  //两个单词没有重复字母
                    int now = lens[i] * lens[j];
                    ans = max(ans, now);
                }
            }
        }

        return ans;
    }
};

int main() {
    Solution solution;

    // 20
    cout << solution.maxProduct({"abcw", "baz", "foo", "bar", "fxyz", "abcdef"})
         << endl;

    // 4
    cout << solution.maxProduct({"a", "ab", "abc", "d", "cd", "bcd", "abcd"})
         << endl;

    // 0
    cout << solution.maxProduct({"a", "aa", "aaa", "aaaa"}) << endl;
}